package stack;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * @Program: dataOJ->PolandNotion
 * @Description: 逆波兰表达式
 * @Author: Tansty
 * @Date: 2022-02-12 21:03
 * @Version： 1.0
 **/

public class PolandNotion {
    public static void main(String[] args) {
        String s = "(32+4)*5-6";
        System.out.println(new PolandNotion().getResult(s));
    }
    /**
     * @Description 将中缀表达式的字符串转为list
     * @author Tansty
     * @date 2022/2/13 22:18
     * @param regex 表达式字符串
     * @return java.util.List<java.lang.String>
     */
    public List<String> getInfixList(String regex){
        ArrayList<String> list = new ArrayList<String>();
        char[] array = regex.toCharArray();
        StringBuilder temp = new StringBuilder();
        for (int i = 0; i < array.length; i++) {
            if(isOperator(array[i])){
                list.add(""+array[i]);
            }else{
                if(i==array.length-1){
                    temp.append(array[i]);
                    list.add(temp.toString());
                    temp = new StringBuilder();
                }else{
                    if(isOperator(array[i+1])){
                        temp.append(array[i]);
                        list.add(temp.toString());
                        temp = new StringBuilder();
                    }else{
                        temp.append(array[i]);
                    }
                }
            }
        }
        return list;
    }
    /**
     * @Description 中缀表达式转为后缀表达式
     * @author Tansty
     * @date 2022/2/13 22:18
     * @param list
     * @return java.util.List<java.lang.String>
     */
    public List<String> infixToSuffix(List<String> list){
        Stack<String> stack = new Stack<String>();
        ArrayList<String> expression = new ArrayList<String>();
        for (String s : list) {
            //但是数字时直接放入表达式的栈中
            if(!isOperator(s.charAt(0))){
                expression.add(s);
            }else if("(".equals(s)){
                //左括号直接压入符号栈中
                stack.push(s);
            }else if(")".equals(s)){
                //遇见右括号，不断将符号栈中的内容弹出放入表达式栈中，直到遇见左括号
                while (!stack.peek().equals("(")){
                    expression.add(stack.pop());
                }
                //将左括号弹出，消掉一对括号
                stack.pop();
            }else{
                //如果当前遍历的符号优先级大于符号栈中的符号，直接压入符号栈
                if (stack.isEmpty() || "(".equals(stack.peek()) ||getPriority(s.charAt(0)) > getPriority(stack.peek().charAt(0))) {
                    stack.push(s);
                }else{
                    //如果优先级小于符号栈中的符号，则需不断将符号栈中的符号弹出
                    //并放入表达式栈中直到优先级大于符号栈的
                    while (!stack.isEmpty() &&getPriority(s.charAt(0)) < getPriority(stack.peek().charAt(0))) {
                        expression.add(stack.pop());
                    }
                    //最后把当前的符号压入符号栈中
                    stack.push(s);
                }

            }
        }
        //最后将符号栈中的全部放入表达式栈中
        while (!stack.isEmpty()){
            expression.add(stack.pop());
        }
        return expression;
    }
    /**
     * @Description 获取操作符的优先级
     * @author Tansty
     * @date 2022/2/13 22:19
     * @param ch 操作符号
     * @return int
     */
    public int getPriority(char ch){
        if(ch == '*'||ch=='/'){
            return 2;
        }else if(ch=='+'||ch=='-'){
            return 1;
        }else {
            return 0;
        }
    }
    public static List<String> getList(String s){
        return new ArrayList<String>(Arrays.asList(s.split(" ")));
    }
    /**
     * @Description 判断是否时操作符号
     * @author Tansty
     * @date 2022/2/13 22:20
     * @param opr
     * @return boolean
     */
    public boolean isOperator(char opr){
        String s = ""+opr;
        return !s.matches("\\d+");

    }
    /**
     * @Description 进行不同符号的计算
     * @author Tansty
     * @date 2022/2/13 22:20
     * @param num1
     * @param num2
     * @param opr
     * @return int
     */
    public int calculate(int num1,int num2,char opr){
        int result = 0;
        switch (opr){
            case '+':
                result = num1+num2;
                break;
            case '-' :
                result = num2-num1;
                break;
            case '*':
                result = num2*num1;
                break;
            case '/':
                result = num2/num1;
                break;
            default:
                break;
        }
        return result;
    }
    /**
     * @Description 获取中缀表达式的结果
     * @author Tansty
     * @date 2022/2/13 22:20
     * @param regex
     * @return java.lang.String
     */
    public String getResult(String regex){
        List<String> list = infixToSuffix(getInfixList(regex));
        Stack<String> stack = new Stack<String>();
        for (String s : list) {
            //判断是否是操作符
            if(isOperator(s.charAt(0))){
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                stack.push("" + calculate(num1, num2, s.charAt(0)));
            }else {
                stack.push(s);
            }
        }
        return stack.pop();
    }
}
